# -*- coding: utf-8 -*-
"""
Created on Sun Sep 20 16:52:57 2020

@author: Administrator
"""

'''

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Follow up:

Could you solve this problem without using the library's sort function?
Could you come up with a one-pass algorithm using only O(1) constant space?
 

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]
Example 3:

Input: nums = [0]
Output: [0]
Example 4:

Input: nums = [1]
Output: [1]
'''

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        '''
        20200920--李运辰
        
        python3自带方法
        nums.sort()
        return nums
        
        
        i=0 1 2 3 4
        l=0 1 2
        r=5 4 3
        2 0 2 1 1 0
        0 0 2 1 1 2
        0 0 2 1 1 2
        0 0 2 1 1 2
        0 0 1 1 2 2
        0 0 1 1 2 2
        
        
        '''
        n = len(nums)
        l,r=0,n-1
        i=0
        while(i<=r):
            if nums[i]==0:
                nums[i],nums[l] = nums[l],nums[i]
                
                l +=1
                i +=1
            elif nums[i] ==1:
                i +=1
            elif nums[i] ==2:
                nums[i],nums[r] = nums[r],nums[i]
                r -=1
        
        